package LeetCode.Leet300_399.Leet370_379.Leet377;

/**
 * @ClassName Solution_1
 * @Author 孙天赐
 * @Date 2025/9/25 17:16
 * @Description TODO: 方法一   动态规划（二维dp）    2ms 9.68%
 *                  如果求组合数就是外层for循环遍历物品，内层for遍历背包。
 *                  如果求排列数就是外层for遍历背包，内层for循环遍历物品。
 */
class Solution_1 {
    public int combinationSum4(int[] nums, int target) {
        int[][] dp = new int[nums.length + 1][target + 1];

        // 初始化第一列
        for (int j = 0; j < nums.length + 1; j++) {
            dp[j][0] = 1;
        }

        // 动态规划
        for (int i = 1; i < target + 1; i++) {  // 背包
            for (int j = 1; j < nums.length + 1; j++) {  // 物品
                if (i >= nums[j - 1]) {
                    // 求排列的情况（不同顺序独立计算），这里的dp[j][i]不能由dp[j][i - nums[j - 1]]推导出来，
                    // 因为dp[j][i - nums[j - 1]]没有考虑j后面的物品，而dp[nums.length][i - nums[j - 1]]则考虑了
                    // 看不懂没关系，完全背包问题重点掌握一维dp的解决方式
                    dp[j][i] = dp[j - 1][i] + dp[nums.length][i - nums[j - 1]];
                } else {
                    dp[j][i] = dp[j - 1][i];
                }
            }
        }
        return dp[nums.length][target];
    }
}
